The present invention relates to methods and apparatus for compressing and expanding bi-level image data, more particularly to methods and apparatus that avoid unnecessary loss of resolution when the image data must be compressed to within a fixed size.
When a bi-level image stored in a computer is printed by a printer, for example, the amount of image data that must be transferred from the computer to the printer is extremely large, so the data are often compressed in the computer, transferred in compressed form, then expanded in the printer. Before being expanded, the data must be temporarily stored in a memory in the printer. Although it is desirable for the printer's memory to be as large as possible, space and cost restrictions normally limit the amount of memory with which a printer can be provided, thus forcing the computer to compress the image data to a size not exceeding a certain limited memory capacity.
To complicate matters, some bi-level images are much harder to compress than others. Images of pages of text are comparatively easy to compress, and can usually be compressed satisfactorily by lossless compression methods. Natural images such as bi-level images generated from photographs, and especially images in which different shades of gray are represented by dot patterns generated using a dithering matrix, are much harder to compress; lossy compression methods must be often employed if adequate compression ratios are to be achieved.
Although lossy compression methods can produce arbitrarily high compression ratios, there is a corresponding loss of resolution when the data are expanded. This effect can be seen, for example, in data compressed according to the progressive reduction standard (PRES) recommended by the Joint Bi-Level Image Coding Experts Group (JBIG). According to this standard, a series of images is created by successively reducing the resolution of a bi-level image, and differential images are produced by taking the differences between successive images in the series. First the most reduced image is encoded and transmitted; then the differential images are successively encoded and transmitted. When the most reduced image is received, decoded, and expanded, the result is an extremely blocky or grainy image showing no fine detail, but as more data are received, the image resolution improves dramatically.
When this method is applied to the transfer of bi-level image data to a printer with a comparatively small memory, however, it may be impossible to transfer more than the most reduced image, resulting in illegible text pages, natural images with a blocky, grainy, or washed-out appearance, and other unacceptable printed output.